Streaming #5 (NOIP 模拟赛 Day 1)
| 题目名称 |
珠 |
免农 |
高维网络 |
| 目录 |
beads |
rabit |
cube |
| 可执行文件名 |
beads |
rabit |
cube |
| 输入文件名 |
|
标准输入 |
|
| 输出文件名 |
|
标准输出 |
|
| 每个测试点时限 |
1s |
1s |
1s |
| 内存限制 |
128M |
128M |
128M |
| 测试点数目 |
10 |
10 |
10 |
| 每个测试点分值 |
10 |
10 |
10 |
| 是否有部分分 |
无 |
无 |
无 |
| 题目类型 |
传统 |
传统 |
传统 |
特别提示：评测在 Linux 下进行，C/C++语言开启-O2 优化开关，Pascal
语言开启-O1 优化开关。
珠
【问题描述】
萌蛋有𝑛颗珠子，每一颗珠子都写有一个数字。萌蛋把它们用线串成了环。 我们称一个数字串是有趣的，当且仅当它的第 1 位是 2，且除了第 1 位以外 的每一位都是 3。例如，2，233，2333333 都是有趣的数字串。 现在，你可以从这串珠子的任意一颗开始读，沿着顺时针或逆时针方向，到 任意一颗珠子停止。这样，你就可以读出一个数字串来。 萌蛋想知道，所有能读出的有趣的数字串当中，最长的是哪一个数字串。当 然，你也可能读不出任何一个有趣的数字串，你也需要对这种情况做出判断。
【输入文件】
输入只有一行，是一个数字串。这是从这串珠子的某一颗开始，顺时针读取 恰好一圈得到的。
【输出文件】
输出只有一行，是能读出的最长有趣的数字串。特殊地，如果找不到任何有 趣的数字串，应输出“TvT”（不含引号）。
【输入样例 1】
323
【输出样例 1】
233
【输入样例 2】
333
【输出样例 2】
TvT
【数据规模和约定】
对于
20%的数据，𝑛 ≤ 3。
对于 40%的数据，𝑛 ≤ 100。
对于 60%的数据，𝑛 ≤ 1,000。
另有 20%的数据，输入的数字串中不含 3。
对于 100%的数据，𝑛 ≤ 100,000。
Solution
签到题，从2开始分两头扫描，O(n)结束。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> using namespace std; char ch[1000100]; int cnt=0,ans=0,pos,flag; int main() { freopen("beads.in","r",stdin); freopen("beads.out","w",stdout); scanf("%s",ch+1); int len=strlen(ch+1); for(int i=1;i<=len;i++)ch[i+len]=ch[i]; for(int i=1;i<=len;i++) { cnt=0; if(ch[i]!='2')continue; cnt++; int j=i+1; while(true) { if(ch[j]=='3')cnt++,j++; else break; } if(cnt>ans)ans=cnt,pos=i,flag=1; } for(int i=len*2;i>len;i--) { cnt=0; if(ch[i]!='2')continue; cnt++; int j=i-1; while(true) { if(ch[j]=='3')cnt++,j--; else break; } if(cnt>ans)ans=cnt,pos=i,flag=2; } if(flag==1){ for(int i=pos;i;i++) { if(i!=pos&&ch[i]!='3')break; else printf("%c",ch[i]); } } if(flag==2){ for(int i=pos;i;i--) { if(i!=pos&&ch[i]!='3')break; else printf("%c",ch[i]); } } if(flag==0)printf("TvT"); return 0; }
|
免农
【问题描述】
（如果你想更好地理解本题，请先阅读 NOI2011 第一试“兔农”一题） 萌蛋近年收入不景气，正在她发愁如何能多赚点钱时，她听到隔壁的小朋友 在讨论免子繁殖的问题。（注：免子是一种简单的单细胞生物） 问题是这样的：时刻 0 有 2 只刚出生的免子。每一时刻，每只免子都会分裂 成为 2 只免子。问时刻𝑛共有多少只免子？ 聪明的你可能已经发现，时刻𝑛的免子数正好是第𝑛 + 1个 2 的幂次。萌蛋不 懂什么叫幂，但她也发现了规律：时刻𝑛 + 1的免子数等于时刻𝑛的免子数的 2 倍。 前几个时刻（从 0 开始）的免子数依次为： 2 4 8 16 32 64 128 256 512 … 萌蛋发现越到后面免子数增长的越快，期待养免子一定能赚大钱，于是萌蛋 在时刻 0 买了 2 只免子开始培养。 每天，萌蛋都要给免子们提供营养。免子的培养基非常特别，每𝑘只免子占 据一个培养基，最后剩下的不足𝑘只占据一个培养基。由于免子特别害怕孤独， 如果某个培养基只有 1 只免子，这只免子就会很快死掉。 然而，每个时刻的免子数仍然是可以计算的。例如，当𝑘 = 7时，前几个时 刻（从 0 开始）的免子数依次为： 2 4 7 14 28 56 112 224 448 … 给定𝑛，你能帮助萌蛋计算时刻𝑛她有多少只免子么？由于答案可能非常大， 你只需要告诉萌蛋时刻𝑛的免子只数对𝑝的余数即可。
【输入文件】
输入只有一行，包含三个整数𝑛 𝑘 𝑝。
【输出文件】
输出只有一行，为一个整数，表示时刻𝑛的免子只数对𝑝的余数。
【输入样例】
6 7 10086
【输出样例】
112
【数据规模和约定】
对于 30%的数据，𝑛 ≤ 1,000,000。
另有 30%的数据，𝑘是𝑝的正整数倍。
对于 100%的数据， 𝑛 ≤ 1,000,000,000,2 ≤ 𝑘 ≤ 1,000,000,1 ≤ 𝑝 ≤ 1,000,000。
Solution
这道题也很傻逼吧。md2011nNOI那一题不知道比这高到哪里去了，还有助于理解，迷醉。很明显第一次死亡之后，免子就不会再死了，所以只要求出免子什么时候第一次死。又很明显：
证明了枚举次数不会超过k次。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int n,k,p; int Quick_Pow(int x,int y,int mod) { int rtn=1; while(y) { if(y&1)rtn=((1ll)*rtn*x)%mod; x=((1ll)*x*x)%mod; y>>=1; } return rtn; } void Pre_Check() { if(k%2==0){ printf("%d",Quick_Pow(2,n+1,p)); exit(0); } } int main() { freopen("rabit.in","r",stdin); freopen("rabit.out","w",stdout); scanf("%d%d%d",&n,&k,&p); Pre_Check(); int cnt=1,pos=-1; for(int i=0;i<=n;i++){ cnt=(cnt<<1)%k; if(cnt==1){ pos=i; break; } } if(pos>=0)printf("%d",((1ll)*(Quick_Pow(2,pos+1,p)-1+p)%p*Quick_Pow(2,n-pos,p))%p); else printf("%d",Quick_Pow(2,n+1,p)); return 0; } printf("%d",((1ll)**Quick_Pow(2,n-i,p))%p); 1000000000 1000009 1000007 */
|
高维网络
【问题描述】
现在有一个𝑑维的坐标网格，其中第𝑖维坐标的范围是[0,𝑎𝑖]。 在这个范围内建立一个有向图：我们把范围内的每个整点（每一维坐标均为 整数的点）当做图上的顶点。设点𝐴(0,0,⋯,0),𝐵(𝑎1,𝑎2,⋯,𝑎𝑑)。 对于范围内的点(𝑥1,𝑥2,⋯,𝑥𝑑)，它会向以下这些点（如果目标点在范围内）： (𝑥1 + 1,𝑥2,⋯,𝑥𝑑),(𝑥1,𝑥2 + 1,⋯,𝑥𝑑),⋯,(𝑥1,𝑥2,⋯,𝑥𝑑 + 1)连有向边。 现在从点𝐴到点𝐵会有若干条路径，路径的条数可以十分简单地算出。然而 不幸的是，范围内有𝑝个点被破坏了（点𝐴和点𝐵不会被破坏），其中第𝑖个点的坐 标为(𝑥𝑖,1,𝑥𝑖,2,⋯,𝑥𝑖,𝑑)。你需要算出从点𝐴到点B剩余的路径条数。 由于答案可能很大，你只需要输出它对1,000,000,007取模的结果。
【输入文件】
第一行为两个整数𝑑 𝑝。 第二行为𝑑个整数，其中第𝑖个数是𝑎𝑖。 接下来𝑝行，每行𝑑个整数，其中第𝑖行第𝑗个数是𝑥𝑖,𝑗。
【输出文件】
一个整数，表示从点𝐴到点𝐵剩余的路径条数对1,000,000,007取模的结果。
【输入样例】
2 1
2 1
1 0
【输出样例】
1
【样例解释】
如图所示，当删掉点(1,0)后，从点𝐴到点𝐵的 3 条路径只剩下了 1 条。
【数据规模和约定】
Solution
这道题还是一道好题，暴力拿了60，也只能拿六十。
首先我们可以考虑如果没有限制点的存在。也就是说每个维的状态从0到ai有多少种方案。运用一些组合数学的知识可以知道（然而我并不会证明）：
对于整道题我们再来使用dp，记dp[i]来表示从起点(0,0)走到第i个限制点的合法方案数，如果到达了i那么后面的所有路径均不合法直接运用我们上面推的算法就可以得到方案数,用A到B的总方案数减去两者的乘积即可。
那么我们注意到这种方法可以对所有情况进行处理，关键在于我们如何得到dp[i]的值，那么其实已经说的很显然了，我们可以把i当成终点进行分治，所有在其左下方的点都要被统计
以上。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #define LL long long #define mod 1000000007 using namespace std; int d,p[510][510],P; LL fac[10000007],inv[100007],a[110],dp[10000007]; LL Quick_Pow(LL x,LL y) { LL rtn=1; while(y) { if(y&1)rtn=(rtn*x)%mod; x=(x*x)%mod; y>>=1; } return rtn; } void Pre() { fac[0]=1;inv[0]=1; for(int i=1;i<=10000007;i++) fac[i]=(fac[i-1]*i)%mod; for(int i=1;i<=100007;i++) inv[i]=Quick_Pow(fac[i],mod-2); } LL Count(int x,int y){ LL rtn=1,sum=0; for(int i=1;i<=d;i++) { int dx=p[y][i]-p[x][i]; if(dx<0)return -1; sum+=dx,rtn=(rtn*inv[dx])%mod; } rtn=(rtn*fac[sum])%mod; return rtn; } LL dfs(int pos) { LL rtn=0; if(dp[pos]!=-1)return dp[pos]; rtn+=Count(0,pos); for(int i=1;i<=P+1;i++)if(pos!=i) { LL c=Count(i,pos); if(c==-1)continue; rtn=(rtn+mod-dfs(i)*c%mod)%mod; } return dp[pos]=rtn; } int main() { scanf("%d%d",&d,&P); for(int i=1;i<=d;i++)scanf("%d",&a[i]); for(int i=1;i<=P;i++)for(int j=1;j<=d;j++) scanf("%d",&p[i][j]); Pre(); for(int i=1;i<=d;i++) p[0][i]=0,p[P+1][i]=a[i]; memset(dp,-1,sizeof(dp)); printf("%lld",dfs(P+1)); return 0; } 2 1 2 1 1 0 */
|
